#include <bits/stdc++.h>
#include <string>
using namespace std;

struct Heap
{
    int *data;
    int capacity;
    int size;
};

struct Heap *initHeap(int capacity)
{
    struct Heap *h = (struct Heap *)malloc(sizeof(struct Heap));
    h->size = 0;
    h->capacity = capacity;
    h->data = (int *)malloc(sizeof(int) * (capacity + 1));
    return h;
}

bool isFullHeap(struct Heap *h)
{
    return h->size == h->capacity;
}

bool isEmptyHeap(struct Heap *h)
{
    return h->size == 0;
}

/** 自底向上渗透 */
void percolateUp(struct Heap *h, int k)
{
    while (h->data[k] < h->data[k / 2] && k > 1)
    {
        int x = h->data[k];
        h->data[k] = h->data[k / 2];
        h->data[k / 2] = x;
        k /= 2;
    }
}

/** 自顶向下渗透 */
void percolateDown(struct Heap *h, int k)
{
    while (k < h->size)
    {
        int x = h->data[k], index = k;
        int left = k * 2, right = k * 2 + 1;
        if (h->data[index] > h->data[left] && left <= h->size)
            index = left;
        if (h->data[index] > h->data[right] && right <= h->size)
            index = right;
        if (index == k)
            break;
        h->data[k] = h->data[index];
        h->data[index] = x;
        k = index;
    }
}

struct Heap *insertToHeap(struct Heap *h, int val)
{
    if (isFullHeap(h))
        return h;
    h->data[++h->size] = val;
    percolateUp(h, h->size);
    return h;
}

struct Heap *removeHeap(struct Heap *h)
{
    if (isEmptyHeap(h))
        return h;
    h->data[1] = h->data[h->size--];
    percolateDown(h, 1);
    return h;
}

void printHeap(struct Heap *h)
{
    for (int i = 1; i <= h->size; i++)
    {
        cout << h->data[i] << " ";
    }
    cout << endl;
}
int main()
{
    struct Heap *h = initHeap(20);
    h = insertToHeap(h, 20);
    h = insertToHeap(h, 50);
    h = insertToHeap(h, 35);
    h = insertToHeap(h, 70);
    h = insertToHeap(h, 65);
    h = insertToHeap(h, 5);
    printHeap(h);
    removeHeap(h);
    printHeap(h);
    return 0;
}